【题解】 [CQOI2015]网络吞吐量 网络流 luoguP3171 | Qiuly's blog!

【题解】 [CQOI2015]网络吞吐量 网络流 luoguP3171

Posted on | Edited on | In | Comments:

题目要求你做什么就做什么呗。

我们先跑最短路，然后按照最短路的边连网络流的边就好了。

这里我选择跑堆优 $Dij$ ，然后我们枚举每一条边，判断着一条边是否为最短路的边，判断的方式很显然，就是看这条边的起点的 $dis$ 加上边权是否等于终点的 $dis$ 就好。

网络流要拆点，除了拆了的点之间连一条该点的权值的边之外，其余的边全部都是 $inf$ ，当然第一个点和第 $n$ 个点拆点后连边也是 $inf$ 而非点权。连完边之后跑最大流即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define ll long long
#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=1e5+2;
const ll inf=1e18+9;

int n,m,s,t;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

namespace Dinic{

    std::queue<int> q;
    struct Edge{int nxt,to;ll val;}G[N<<1];
    int cnt(1),dep[N],head[N];

    inline void add(int u,int v,ll w){
        G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
        G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
    }

    inline bool bfs(){
        memset(dep,0,sizeof(dep)); 
        q.push(s);dep[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=G[i].nxt){
                int y=G[i].to;
                if(dep[y]||G[i].val<=0)continue;
                dep[y]=dep[x]+1,q.push(y);
            } 
        }return dep[t];
    } 
    inline ll dfs(int x,ll flow){
        if(x==t||!flow)return flow;
        ll used=0,rlow;
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]==dep[x]+1&&G[i].val){
                used+=(rlow=dfs(y,min(G[i].val,flow-used)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        }if(!used)dep[x]=-1;
        return used;
    }

    inline ll dinic(){
        ll maxflow=0;
        while(bfs())maxflow+=dfs(s,inf);
        return maxflow;
    }
}

namespace Dijstra{
    #define P std::pair<int,int>
    std::priority_queue<P,std::vector<P>,std::greater<P> > q;
    
    int vis[N],head[N],cnt;
    ll dis[N];
    struct Edge{int nxt,to;ll w;}G[N<<1];
    
    inline void add(int u,int v,ll w){
        G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].w=w,head[u]=cnt;
        G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].w=w,head[v]=cnt; 
    }
    
    inline void dijstra(int s){
        for(int i=1;i<=n;++i)dis[i]=inf;
        memset(vis,false,sizeof(vis));
        dis[s]=0;
        q.push(std::make_pair(dis[s],s));
        while(!q.empty()){
            int x=q.top().second;
            q.pop();if(vis[x])continue;vis[x]=true; 
            for(int i=head[x];i;i=G[i].nxt)
              if(dis[G[i].to]>dis[x]+G[i].w){
              	 dis[G[i].to]=dis[x]+G[i].w;
                 if(!vis[G[i].to])q.push(std::make_pair(dis[G[i].to],G[i].to));
              }
        }
        for(int x=1;x<=n;++x)
            for(int i=head[x];i;i=G[i].nxt)
                if(dis[x]+G[i].w==dis[G[i].to])
                    Dinic::add(x+n,G[i].to,inf);
        return;
    }
}

int main(){
    IN(n),IN(m),s=1,t=n<<1;
    for(int i=1;i<=m;++i){
    	int u,v,w;IN(u),IN(v),IN(w);
    	Dijstra::add(u,v,w);
    }
    Dijstra::dijstra(1);
    for(int i=1,x;i<=n;++i)
        IN(x),Dinic::add(i,i+n,(i!=1&&i!=n)?x:inf);
    printf("%lld\n",Dinic::dinic());
    return 0;
}

本文标题:【题解】 [CQOI2015]网络吞吐量 网络流 luoguP3171

文章作者:Qiuly

发布时间:2019年03月13日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/03/13/[题解]luoguP3171/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。